package org.example.myleet.p1239;

import java.util.*;

/**
 * 位运算 + 所有可行方案的遍历
 * 在一个32位整型内用1记录出现过的字母，上限是26个字母即26个1
 */
public class Solution {

    /**
     * 记录可行方案组成的片段，以及片段对应的位数
     */
    static class Signature {
        String fragment;
        int signature;

        public Signature(String fragment, int signature) {
            this.fragment = fragment;
            this.signature = signature;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Signature signature1 = (Signature) o;
            return signature == signature1.signature;
        }

        @Override
        public int hashCode() {
            return Objects.hash(signature);
        }

        @Override
        public String toString() {
            final StringBuilder sb = new StringBuilder("Signature{");
            sb.append("fragment='").append(fragment).append('\'');
            sb.append(", signature=").append(Integer.toBinaryString(signature));
            sb.append('}');
            return sb.toString();
        }
    }

    public int maxLength(List<String> arr) {
        List<Signature> signatures = new ArrayList<>(arr.size());
        for (int i = 0; i < arr.size(); ++i) {
            int signature = 0;
            String fragment = arr.get(i);
            boolean retain = true;
            for (int j = 0; j < fragment.length(); ++j) {
                char c = fragment.charAt(j);
                //字母对应的数位
                int offset = c - 'a';
                if (((signature >> offset) & 1) == 1) {
                    //如果数位对应的字母以及存在，则这个字符串fragment不用考虑，不加入到signatures集合中
                    retain = false;
                    break;
                }
                signature = signature | (1 << offset);
            }
            if (retain) {
                signatures.add(new Signature(fragment, signature));
            }
        }
        if (signatures.size() == 0) {
            //没有得选
            return 0;
        }
        //记录所有可能的组成方式
        Set<Signature> all = new HashSet<>();
        all.add(signatures.get(0));
        //第一个作为初始化
        int maxLen = signatures.get(0).fragment.length();
        for (int i = 1; i < signatures.size(); ++i) {
            List<Signature> newSigs = new ArrayList<>();
            for (Signature a : all) {
                if ((signatures.get(i).signature & a.signature) == 0) {
                    //如果其中一种组合方式与第i个signature没有字母重复，则这两个片段可以组合成新片段，并考察新长度
                    String newFragment = signatures.get(i).fragment + a.fragment;
                    int newSig = signatures.get(i).signature | a.signature;
                    newSigs.add(new Signature(newFragment, newSig));
                    maxLen = Math.max(maxLen, newFragment.length());
                }
            }
            //或者signature自己加入到待选可能性中
            all.add(signatures.get(i));
            maxLen = Math.max(maxLen, signatures.get(i).fragment.length());
            all.addAll(newSigs);
        }
        return maxLen;
    }
}
